/**
 * 题目：写一个算法实现：将文件路径数组转化树状结构。
 * 
 * 
 * 输入：
 * [ 
 *   'root/file1.js', 
 *   'root/folder1/file2.js', 
 *   'root/folder2/file3.js', 
 *   'root/folder2/subfolder1/file4.js'
 * ]
 * 
 * 
 * 输出：
 * {
 *   name: 'root',
 *   children: [
 *     { name: 'file1.js' },
 *     {
 *       name: 'folder1',
 *       children: [{ name: 'folder1'}],
 *     },
 *     {
 *       name: 'folder2',
 *       children: [
 *         { name: 'file3.js' },
 *         { name: 'subfolder1',
 *           children: [ {name: 'file4.js'} ]
 *         }
 *       ],
 *     },
 *   ]
 * }
*/

function pathsToTree(paths) {
  if (paths.length === 0) return null
  // 定义最外层数据
  const rootName = paths[0].split('/')[0];
  const tree = { name: rootName, children: [] }

  // 存path和tree节点关系
  const nodeMap = new Map()
  nodeMap.set(rootName, tree) 

  for(const path of paths) {
    const parts = path.split('/')
    let currNode = tree;

    for(let i=1; i < parts.length; ++i) {
      const part = parts[i]
      const nodeKey = `${currNode.name}/${part}`
      let childNode = nodeMap.get(nodeKey)

      if (!childNode) {
        childNode = { name: part }
        currNode.children.push(childNode)
        nodeMap.set(nodeKey, childNode)

        if (i < parts.length - 1) {
          childNode.children = []
        }
      }

      currNode = childNode
    }
  }

  return tree
}


// 测试
const filePaths = [ 
  'root/file1.js', 
  'root/folder1/file2.js', 
  'root/folder2/file3.js', 
  'root/folder2/subfolder1/file4.js'
]
const tree = pathsToTree(filePaths)

console.log(tree)
// {
//   name: "root",
//   children: [ 
//       { name: "file1.js" },
//       {
//         name: "folder1",
//         children: [{ "name": "file2.js" }]
//       },
//       {
//         name: "folder2",
//         children: [
//            { name: "file3.js" },
//            { name: "subfolder1",
//              children: [{ "name": "file4.js" }]
//            }
//         ]
//       }
//   ]
// }
